package solutions.contest.week272;

import solutions.lib.BaseSolution;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/contest/weekly-contest-272/problems/minimum-operations-to-make-the-array-k-increasing/">2111.使数组 K 递增的最少操作次数</a>
 */
public class Solution2111 extends BaseSolution {

    static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }

        int getLen() {
            return next == null ? 1 : next.getLen() + 1;
        }

        boolean checkVal(int val) {
            if (val < this.val) {
                if (next == null || next.checkVal(val)) {
                    this.val = val;
                }
                return false;
            } else {
                return true;
            }
        }
    }

    public int kIncreasing(int[] arr, int k) {
        int r = 0, n = arr.length;
        for (int i = 0; i < Math.min(k, n - k); i++) {
            int t = i + k, c = 1;
            Node root = new Node(arr[i]);
            while (t < n) {
                c++;
                if (root.checkVal(arr[t])) {
                    Node node = new Node(arr[t]);
                    node.next = root;
                    root = node;
                }
                t += k;
            }
            r += c - root.getLen();
        }
        return r;
    }

    public static void main(String[] args) {
        Solution2111 solution = new Solution2111();
        int r = solution.kIncreasing(new int[]
                        {4,1,5,2,6,2}
                , 3);
        System.out.println(r);
    }
}